package lc.q151_200;

import java.util.*;

/**
 * DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
 *
 * 例如，"ACGAATTCCG" 是一个 DNA序列 。
 * 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
 *
 * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
 */
public class Q187 {

    Map<Character, Integer> map = Map.of(
            'A', 0,
            'C', 1,
            'G', 2,
            'T', 3
    );

    public List<String> findRepeatedDnaSequences2(String s) {
        // 本质就是查询长度为10的子序列
        if (s.length() <= 10) {
            return List.of();
        }

        // 放一个指针
        List<String> res = new ArrayList<>();
        int x = 0;
        for (int i = 0; i < 9; i++) {
            x = (x << 2) | map.get(s.charAt(i));
        }
        Map<Integer, Integer> counter = new HashMap<>();
        int p = (1 << 20) - 1;
        for (int i = 0; i <= s.length() - 10; i++) {
            // 只取后20位
            x = ((x << 2) | map.get(s.charAt(i + 9))) & p;
            counter.put(x, counter.getOrDefault(x, 0) + 1);
            if (counter.get(x) == 2) {
                // 数字转字符串
                res.add(s.substring(i, i + 10));
            }
        }
        return res;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        // 本质就是查询长度为10的子序列
        if (s.length() <= 10) {
            return List.of();
        }

        // 放一个指针
        List<String> res = new ArrayList<>();
        Map<String, Integer> counter = new HashMap<>();
        // 优化，使用一个map记录
        // 再次优化，因为总共只有四个字母，能否用位表示呢
        // 方法就是定义x，存最开始的十个数，然后不断地左移，并将前两位变成0
        for (int i = 0; i <= s.length() - 10; i++) {
            String subStr = s.substring(i, i + 10);
            Integer count = counter.getOrDefault(subStr, 0);
            counter.put(subStr, count + 1);
            if (count == 1) {
                res.add(subStr);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Q187().findRepeatedDnaSequences2("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
    }
}
